Apple recently sent out the new logo for WWDC 2013 (Worldwide Developer's Conference) and, well, it's colorful.
Now, if you know anything about Apple events, you probably know Apple likes to vaguely hint at coming surprises with what they send to press. So, what could they be hiding in the new logo? Well, I have three ideas:
Obviously, the move to a much, much thinner typeface. This is actually Helvetica Neue Pro UltraLight rather than the iOS mainstay Helvetica. (Yes, there's difference, heh). This obviously leads one to believe they're moving to the more "flat UI" that Google and Microsoft have transitioned to. (Tall, thin fonts are a part of Swiss Metro and Holo design). Thank God they are hopefully doing this because iOS has been seeming mighty stale, recently.
Next, the rounded rectangles seem to be in an odd stack-like formation. This could be one of three things; a new folder system, apps that are less sandboxed (they're "merging"), or a new wiggle-related animation? Well, I think it connects to the first option because this seems to be an image promoting the possibly new UI. So, I think this is what a folder will look like on iOS 7; a bunch of semi-translucent papers stacked on top of each other in a chaotic but ordered way.
Finally, and most importantly, I think Apple showed us the new color palette for iOS 7! Look at those bold, over-saturated, and beautiful colors! Those have to correlate to iOS's new "texture-less UI," right?
With number 3 in mind, I decided to create a color palette for iOS 7 based on this logo:
Pretty colors, no?
Sadly, I didn't stop there. I decided to try and mock up what iOS 7 could look like with app icons that were flat and used these colors. Please note that I am not an artist; the following will be very rough and I apologize for possibly hurting your eyes. Also, this isn't what I'm proposing iOS 7 will look like, just what the current iOS would look like using the app icons, fonts, and folders hinted at by the WWDC logo. Without further ado:
Safari's icon is "rough'n stuff'n robots..."
Personally, I like the look. If Apple were to go with there flat icons, I imagine they'll look something like the above solely because they can't change too much without scaring away their massive user base. For example, if they were to actually use the design and colors provided, I can't imagine the Phone icon looking that different from the one I created.
So, I just thought I would make a quick post about the WWDC logo in the time I should be studying for my finals. Any thoughts? Any disagreements? I'd love to hear about them in the comments! Want to tell me how much iOS suxz? Well, I'd love to hear your comments, too! Just send them to /dev/null and I'll read them at my earliest convenience!
About two weeks ago, I dropped my iPhone 5 on the sidewalk and somehow ended up cracking both of the glass panes on the back of my iPhone 5. (Seriously, how does that happen)? The next day, I called Apple because I was sure it wouldn't cost an abhorrant amount of money to replace two tiny pieces of glass. Well, as you may have guessed, I was wrong. Apple wanted ~$250 to fix my iPhone 5 or it was out of warranty. (Let me just say that after doing all of this work and knowing Apple wouldn't replace the glass but the whole back frame of the iPhone, this makes a tiny bit of sense). Anyways, I Google'd how to replace it and there weren't any answers or tutorials, so I set out on my own to fix an obscure part of the iPhone's parts list! So, without further ado, here's how to replace the iPhone 5's top and bottom back glass.
The Parts List!
I purchased many things from eBay and Amazon but these aren't recommendations for these sellers, they're more of suggestions.
This iPhone-opening kit. It included two prying tools, a small pentalobe screwdriver, a small philips screwdriver, a guitar pick, and a suction cup. All of these were needed for the operation!
This adhesive. This will be used to secure the glass to the frame. I used an xacto knife to cut the pieces.
This heat gun. Used to loosen adhesive. Also, it's totally awesome to have a heat gun.
So, total bill of materials: about $36. For those doing the math at home, yes $36 < $250.
The Process
Now, I'm not going to step you through taking the iPhone 5 apart, but I will link you to iFixit's amazing guide and discuss my thoughts on the process. Also, please note that this isn't for beginners and should only be attempted by those who know what they're doing! I assume no responsibility for your broken device and all that jazz.
Step 23A: disconnect the cable on the bottom left!
So, start the process and deal with separating the screen from the frame (it will take awhile, you will get frustrated). Continue through to step 12 where I think I should mention that the commenter is wrong about disconnecting the battery; it does NOT ruin the battery. Everything will be fine once it's reconnected! Also, I noticed that using the guitar pick to slide under the battery to sever the adhesive worked wonders! Now, proceed until step 24 and then STOP. One commenter was correct in pointing out that iFixIt forgot a step here; you need to disconnect the cable that connects the the logic board above the right speaker! They already pealed it back in their photo of Step 23 so just emulate what they did. Finally, continue until step 30 and then halt.
From here, there are two things that need to be done. One is (if your device is like mine) you need to remove the flash diffuser. Mine looked like a tiny reflective box over the camera flash's location on the back. Remove it and the plastic flash from the glass. Next, use the top of a plastic tool to gently push out on the camera lens; the lens cover should pop off so you should put it in a safe place.
From here, we have everything we need to fix the glass! So, get out a large piece of paper (or some form of catch-all surface) and put it beneath your iPhone. Next, plug in the heat gun and let it get ready for a second. Also, grab a heat-proof glove of some sort (I used an oven mitten)! Now, hold the frame with the mit and turn the heat gun on (I used the High setting because I'm daring) and run it over the top piece of glass. I held it about 2 inches away and went back and forth over the whole piece for about 45 seconds. Now, turn it off, set it up right, and then grab your screw driver. From the inside of the iPhone, you should see some small holes where the glass is located. Push out on these with the screwdriver and the glass should eventually give out. NOTE: It will crack. It will shatter. It will make a mess. Always remember to wear gloves and protective eyewear!
Once the hole in the frame is clear of glass, turn to the removed pane. You should see a plastic black frame connected to the camera lens hole and one connected to the flash hole. Remove them and set them aside. Now, repeat this process with the bottom piece of glass!
Once done, you should take the adhesive and cut out small strips that you think would firmly secure the new glass and attach them to the panes. Once reseated, turn the device around and find the camera area. Put the plastic frames you recovered from the pane and put them in the inside of the frame. Finally, you're free to reassemble your device! Oh, you should put the glass lens protector back in through the back of the phone and it should just stay. Now that that's done, you have a fully working iPhone 5 and your warranty in tact for only $36! Take that, corporate America! :)
So, about a month ago, I decided to create a Tumblr. (Note: I'm not sharing my personal "blog;" sorry). While many people have used the social network for the last few years, I never quite "got it." Though, in my quest to stay current and understand why people are using certain services, I set out on creating a profile. The following are my beliefs on why the website is so popular and why users return to it. Also, please note that this is more of an analysis on why users return to the site, not an analysis on what's wrong with the design or what makes the site special.
Finding #1: This Isn't a "Normal" Social Network
One of the first things I learned about Tumblr was that it's not like Facebook, Google+, or Twitter in that it's a "social network" mostly for strangers. I'm not trying to impress my friends, family, or coworkers; I'm trying to connect with others on a global scale. This small difference has several large impacts on the site's users. For one, I was no longer attached to my own life! I was no longer defined as "that guy who played percussion" or "that guy who moved to Oregon to work with Intel;" I could be anyone I wanted to be. My identity was reset and I was allowed to create an Internet personality based solely on my interests or others' interests that I thought were interesting. In my opinion, this is a huge benefit that Facebook, et. all can't replicate; the users are free to be whoever and whatever they want to be in real life. Examples of this include gay high schoolers who are finally able to express their inner-selves in some public facet or people without money "reblogging" high-end fashion despite it being out of their price range. People love talking about themselves and now they love showing their true (and to some extent ideal) selves.
Finding #2: Tumblr: The Fountain of Content
Companies need to learn how to engage their users to keep their userbase. People obviously don't repeatedly return to websites they find boring. So what makes Tumblr so "addictive?" There are three highly-addictive reward systems that are extremely powerful. The first is the user's "Dashboard." Thanks in part to Finding #1, the Dashboard should be filled with content tailored directly towards you. I would describe it as a mixture of Facebook's News Feed, Reddit's homepage, and crack. Due to most posts being images or text, scrolling through a dozen posts on the Dashboard takes seconds. It's a constantly replenished source of content that you know you'll enjoy. The Dashboard also has infinite scrolling enabled so users aren't jarred back to reality after X amount of posts. These two facts make Tumblr extremely addicting to visit. Though, Tumblr isn't just about visiting; it's about sharing.
Finding #3: Followers! Followers! Followers!
The second reward system on Tumblr is the amount of "followers" one has. It's an odd form of social validation; if you get a new follower, you feel like they "like" you. Due to this, the user seemingly tries to be more interactive on the site in hopes of impressing them and convincing others to follow their blog. This near-instant validation leads to users getting caught in a cycle; to get another follower you have to interact more which leads to more followers which leads to more interaction, and so on, and so on. As an aside, Tumblr did something remarkably intelligent; they made your follower count private. This reminds me of a decision Facebook made years ago regarding wall posts. If I remember correctly, due to fears of people comparing wall post counts and feeling inadequate, Facebook removed the number from their site. Tumblr, on the other hand, has made their follower count private which means no one feels bad about their count and they have a gauge on how "popular" or "liked" they are.
Finally, the third reward system is likes and reblogs. This is very similar to the second reward system, but it shows you not only how many people like your content, but what they like. This allows the user to tailor their blog to hone in on what they know will be "popular" amongst followers.
Conclusion: There Are Many Things Others Can Learn From Tumblr
After my first month on Tumblr, I can see what other companies should learn from this site. I've listed these thoughts below and I hope to hear about others' opinions on the subject!
Put the users first and get out of the way. No one wants to use your service; they want to express themselves or help their lives and the less they have to deal with you the better.
Gone are the days of static content. Today, the user needs to be able to determine your site's content and should be able to perfectly tailor it to their identity.
If users are allowed to fully express who they are on the inside, you most likely have a disruptive product.
Implement rewards systems that are less about arbitrary "scores" (Klout) and more about sociability and validating the user's identity.
People are becoming more private and weary about posting their lives online. Allow users to remain public yet private! Tumblr allows people to blog about their lives or remain 100% anonymous. This freedom allows the platform to be used in various ways without hurting the either experience. For example, a user could use a Tumblr to blog about color palettes or they could use it to upload photos of their daily lives. Either way, the platform supports both degrees of privacy.
Implementing infinite scrolling is dangerously addictive and you should always use it. Always.
Note:I know I never finished my series on cracking Reddit's CAPTCHA; I'll finish that soon! Note 2:If these gestures are implemented into an app, I would really like to be notified, credited, or at least contacted. Taking one's ideas and then selling them as your own for $50 is a really inconsiderate and greedy thing to do, and frankly, I would never want to work with you.
Introduction to the Market
So we are at an interesting point in the technology sector right now; we're seeing tablet sales soar and the traditional desktop/laptop market shrink. Many argue this might lead to the "demise" of PCs or that people are just buying tablets as "secondary devices," but this isn't what I want to talk about. Far too many people get caught up in hypothetical analytics in where the market's going rather than discuss where they could take the market. That's what I'm going to talk about today.
Recently, Forrester surveyed almost 10,000 Fortune 500 employees on their tablet usage. Of the respondents, 32% said they desire to use a Windows 8 tablet at work, 26% said iPad, and a mere 12% listed Android. Once again, I'm not here to discuss what OS people hypothetically want; I'm here to think deeper about this. These hypothetical numbers are interesting but the real news comes in the form of the distribution of people currently using tablets in the workplace and how many want to. Only 21% of these workers said they use a tablet as a work device but 17% said they don't have a desire to use them. That implies that 83% of Fortune 500 employees want to use tablets in their daily workflow! So, why hasn't this panned out for them? I blame the lack of excellent Office-esque applications!
The Issue With Document-Based Apps
Making a word processing app is hard. It's not hard in the traditional sense of development; it's hard because there are so many features and tablet UI's call for simplicity. How is it possible to make a clean, touch-based UI if you have to add buttons for tables, fonts, insertions, spell check, file operations, different views, citations, and much more? This is the question that has puzzled developers and designers for the last few years but that doesn't mean people haven't tried to fix it.
Enter Apple with Apple Pages. It's a very attractive app that offers many powerful features, but it's mainly a desktop application. Notice that the UI elements are tiny which means users have to hunt for certain buttons and aim precisely which is a paradigm that's only useful for a cursor. If people were typing a paragraph and then had to bold a word, the workflow would be:
Type > Look up > Hold finger over certain word > Hit "Select" > Find Bold button > Press it
As you can imagine, this is a terrible experience for people who just want to pump out documents quickly. If your workflow has to involve the user hunting, aiming, and moving their arm around a 9 inch screen, then you're obviously not doing it correctly.
Next, we should look at Microsoft's attempt: Office 2013. Office 2013 is an interesting beast because it attempts to add Metro- err- the New Windows UI design to the entire suite of tools while still retaining all of the functionality users know and love. How exactly did Microsoft tailor Office for touch screens, then? Well, they really didn't.
As you can see, the UI elements in the app are legitimately the same (or nearly the same) as a desktop application. They've altered the fonts and spacing to be more "tablet-friendly" but that's really the only differences that shine through. While the Ribbon UI supposedly works well (I have my gripes but that doesn't belong in the scope of this post), it doesn't actually translate well to a finger-based input system. To insert a photo, the user would have to lift their head to the top bar, hunt for the "INSERT" header, tap it with immense precision (it's just one word...), hunt for the now-visible "Photo" button and finally tap it. Once again, this is not an ideal workflow; it's time-consuming and ultimately confusing.
So, after looking at these apps created by these computer juggernauts, I hope you could see why tablets aren't popular for document creation. Beyond the UI of the apps, there's the notion that users will presumably carry around an external keyboard rather than using the on-screen keyboard which is a problem in and of itself. So, what can we do about this?
Anyone Can Point Out an Issue; The Greats Propose Solutions
Gestures! Say it with me: gestures! Y'know, there's something to be said about the two biggest proponents for gestures not implementing them into their word processing apps. (Apple pushed two-finger scrolling, pinch to zoom, swipes, etc. and Microsoft's Windows 8 is basically all gesture-based).
In the modern age of application design, gesture-based input is the holy grail of UI implementation. If done correctly (ex: pinch-to-zoom), the gestures will feel intuitive and easy to understand. Though, if done incorrectly (ex: Google dividing the status bar in Android into two invisible sections that respond differently upon a swipe down), the user might be confused and annoyed when trying to do them. This leads the user to dislike the UI and, most tragically, not use a certain feature or app entirely. Knowing this, it's extremely important to "get it right" so the UI is intuitive enough for the user to understand the gestures and be quick enough that the user's workflow is fluid.
Now, I don't have all of the solutions; heck, I don't even have a tenth. Though, I do have ideas on how the UI should work! Here are some of my ideas and a few mockups/examples:
Text Input
Obviously, the on-screen keyboard will have to be used. This is fine to a certain extent, but it can be vastly improved. Going off iOS, the workflow of selecting text is a mess. The user types what they want but then have to move their finger to where they want, press-and-hold over the word they want, release, wait for the pop up, hit select, and then finally move the second cursor over the scope of their selection. We can do better.
Looking at an iOS jailbreak tweak named SwipeSelection, it's easy to see how simple text selection could be. To move the cursor, the user just swipes left or right on the keyboard. It just works. Now, my proposal to improve this would be to include a better way to select text. One finger swipe moves the cursor but two fingers could be used for both cursors. So, the user finds where they want to move the cursor to with their right hand and then they use their left index finger to move the (now-visible) left-hand cursor. This turns the workflow of text selection to the user types, swipes their right index finger on the keyboard (essentially not moving far), and then the left index finger swipes left or right. That saves a lot of time and is pretty intuitive! Now that that's worked out, lets move on to what one does after selecting text.
Font Operations
Once the text is selected, there are only a finite amount of operations the user would like to do. These include font size alterations, font color, bold/underline/italicize/strikethrough, highlight, make a link, and delete. The delete function is obvious here, but let's try and tackle the other features.
To solve the font color operation, we rely on a simple press-and-hold gesture on the typing area after selecting text. This would then bring up a color wheel around the finger where they user can just swipe over the color they'd like (a la Android Jelly Bean's unlock gesture). I've created a quick mockup (please ignore the absence of "selected text") which you can see here. This turns a hunt-and-aim workflow into a simple tap-and-hold followed by a swipe. It really couldn't be simpler, in my opinion.
Great, now let's work on font size. This is simple and intuitive; once the text is selected, the user should be able to pinch in or out on the text area (like above) and the font would be altered based on that. I don't really think I need to go into too much explanation here.
Next, we should try to create a quick and intuitive way to implement bold/underline/strikethrough. This is tricky because these operations have never manifested themselves as more than just a group of buttons. So, going with the paradigm we've created above, we could devote the left screen to a similar gesture as font color. This means tapping and holding the right side of the text area would yield the color ring whereas the left-hand side would yield another ring; the attribute ring. (Name can obviously be improved). It's the same concept, just with less intuitive options which yield an initial minor hunting game. Theoretically, this ring could also hold the hyperlink and highlighting operations. Since these two rings are extremely similar, it's easy to see that users could grasp one easily which would improve their chances of grasping the other!
Menu Systems
The next challenge is the menu system. As seen in Office 2013, compartmentalizing the location of similar operations is extremely useful! Though, Microsoft seemed to use the desktop system of menu selection and even used a form of Ribbon UI, which is found in Explorer and older versions of Office. Basically, they didn't do much in the way of tablet-izing their menus. Here's how we can change that.
Suppose there was a menubar-typed line of text similar to how Microsoft does it (I really like the capitalized categories). This bar would have compartmentalized categories based on types of operations; file operations, text edit operations, insertion operations, table operations, etc. The bar would be located above the keyboard (or alternatively on the top but that would make the user move their hands more). This would look like this:
Now, here's the interesting part; you don't just click on the label you want and have new options appear somewhere (Ribbon UI...), the menu is gesture-based! The user could press-and-hold on a certain menu item and a list of options would expand upwards and downwards. Also, the faint blue glow would appear on the bar where the operation was selected. Now, the user just moves their finger up or down which would cycle through the list until the option they wanted was in the blue center. Once done, they release their finger to select said operation. I know this is slightly confusing to read, so take a look at this:
Once the user opens the secondary menu, they slide their finger downwards to move "Photo" into the blue area and then they release their finger.
From a usability standpoint, I believe this is great! If you think about it, the selection box (the blue area) would read "INSERT" and then "PHOTO." This is perfect for easily explaining what exactly is occurring. Also, it would be a quick gesture that everyone knows (press-and-hold and slide up or down). On top that, the entire menu could be customizable so the user could move the categories into the position they'd like so the UI would be less hunting-based and more based on personal preferences. All in all, this would reduce the workflow from "move hand to top of screen, look for category, click category, look for option, move hand, click option" to "look for category, press-and-hold category, slide finger up, release finger." Much better, IMO.
Conclusion
There are so many other things that need to be implemented but I hope I successfully demonstrated how gestures can be used in-place of standard desktop UI widgets. I really hope word processing tablet apps improve over time because there's a HUGE market for business apps; we just need people creative enough to fill that gap!
Alright, so now that I went through the general background information, let's get into some specifics and actually interesting information!
To actually get a good sample set, I used a web scraping Chrome plugin in to go to the login page and download the page's CAPTCHA image. This method led me to having roughly 300 CAPTCHA images to aid me in cracking Reddit's security system.
From here, I decided to buy a textbook on Artificial Intelligence/Machine Vision. I ended up buying this book, which seems to be pretty popular and influential when it comes to AI. I read over algorithms related to machine vision such as edge detection, character recognition, ellipse detection, and more. With these algorithms in my back pocket, I decided to try my hand at the supposedly impossible.
Step 1: Remove Extra Colors and Background Noise
To give you an idea of how the program worked, I'll be providing an example here. The following image is a real CAPTCHA that came from Reddit.
QVHZUR
To begin, I decided to write an application that converted the image to one with 4 bpp color. I thought it would serve as a way to lower the amount of colors and hopefully make it easier to detect what was in the image. As luck would have it, the conversion actually really helped! The following is the image with 4 bpp color.
4 BPP CAPTCHA
You might not notice that much of a difference, but there's actually one very large difference between this and the previous image; the grid is now mostly a solid gray with a bit of white, rather than many different colors spanning white to gray. Also, this meant that the foreground letters were basically the only white objects in the image. So, with this knowledge in hand, I wrote a BFS-like algorithm that traverses the image's pixels looking for the white color (-1 in Java) and replaced it with black. Any other color was set to -1, or white. This lead to an amazing milestone; I had successfully removed the grid and created an image with only the letters and some artifacts!
Success!
Step 2: Removing Artifacts
Obviously, the next step was to remove those extraneous artifacts. To do this, I wrote a few algorithms to determine whether a black pixel was extraneous or not. One of these algorithms was to find every black pixel and check how many surrounding pixels were black. If I found many, then the pixel most likely belonged to a letter, and if there were very few, then it was most likely extraneous. Another of these algorithms was to count how many black pixels were in each row. If there were a lot, then the word was presumably there. If there were few, I would erase lines 0-i (i being the row with a few black pixels) or i-height, depending on where in the image the algorithm was.
Alright, getting there...
Alright, this ends part 2. Sorry about the crazy amount of posts, but I'm a student and I don't have a lot of time to write this all out immediately. The next part should cover separating the letters and possibly recognition of them. Thanks for reading and I hope you'll stick around for the next post!
It was a brisk March day when I hurried into one of my favorite professor's offices to basically beg him to sign off on me having an independent research class so I could stay a full-time student. "Sure," he said, "but what exactly do you want to do?" My original idea was to research malware through NFC/RFID chips because I honestly believe that could be a big issue in the future (maybe more on that later). He responded that he had no idea about the subject, but allowed me the opportunity to research it for college credit. "Maybe I'd learn something I could share with him," he questioned? "What's the harm in allowing a student to have college credit for researching security vulnerabilities?" Well, I decided to forego my original idea and instead crack the "homepage of the Internet." NOTE: I will not be sharing any of my code for multiple reasons. One reason is that I do love reddit and would be saddened to see it get overrun by script kiddies and spambots. The second reason is that, if you're smart enough, you should be able to do this on your own. I'm not here to hold your hands to do something malicious; I'm here to inform people on how our current online security systems are unsafe.
A Little Background: What's a "Reddit?"
Reddit is the self-described "homepage of the internet." It's an extremely popular social media platform that involves users sharing, commenting on, and judging links to pictures, articles, music, videos, or self-typed posts. Basically, it's what your homepage should be. The site has millions of users and is currently ranked 136 on Alexa, though I imagine it should be much lower but Reddit's demographic probably doesn't install the Alexa Toolbar... You don't need an account to look at comments or links, but you do need one to comment, vote on links, "subscribe" to subreddits, and more. Creating an account is easy, as visible here:
All one needs to do is supply a username, a password, and a proper response to their CAPTCHA. Here lies our attack vector: to create an account on one of the most popular websites in the world, you only need to provide a name, password, and the response to a small vision-based puzzle.
A Little More Background: CAPTCHA, Eh?
A CAPTCHA is defined as a "Completely Automated PublicTuring test to tell Computers and Humans Apart" (thanks Wikipedia!). Basically, it's the funny-looking jumbled up letters you have to type in to "prove that you're human" on many sites. The point of these images isn't to annoy you; it's that they're supposed to be impossible (read: very hard) for computers to comprehend. If computers could understand how to decipher these images, then scripts could be written to create thousands or millions of spam accounts that would overrun a website. (See, this is why I'm not sharing my code)! Anyways, there are three types of obfuscation in a CAPTCHA:
Warped letters
Color-based tricks
Background noise
As you can see above, Reddit employs all of these. The laters are indeed warped and move in a way that is pretty abnormal. The purpose of this effect is that a machine would have a hard time thinking that slanted 'J' is a normal-form 'J.' They use a trick where the background is black, the intermediate level is white/gray, and the foreground letters are white/gray. This makes it extremely difficult for computers to understand what exactly is a letter and what's the background. Finally, the distorted grid in the back is obviously noise used to make it difficult for a machine to understand what's in the image. See, our sight allows us to view the image as a whole and know what we're looking at. Computer software isn't so lucky; it has to go through the image pixel-by-pixel and judge what it's looking at on a small scale rather than a holistic view.
This ends part one of my write up on how I cracked Reddit's CAPTCHA system. The next part should go over how I separated the letters from the background and then from each other. I hope this series is interesting to some, but if not, at least it's interesting to me!
Hello! I'm going to start a series on my blog (well, technically it will be all that's here as of now) where I go over a lot of the information one needs for a Software Engineering job interview. My first post in the series will be going over Linked Lists, their uses and how to implement them in Java. So, let's start then!
What exactly are Linked Lists, you say?
In computer science, there are many abstract data types that are used to store and access data. One of these numerous abstract data types (which will be referred to as ADT from now on) is a Linked List. A Linked List is a pretty fundamental concept that most applicants should understand. The structure is pretty simple and can be summarized in a bullet-point list:
A collection of "nodes" that point to each other, where the last node points to NULL
Usually, the structure comes in 2 types, a singly linked list or a doubly linked list
Singly linked lists only have one entry point, and it's usually the "head" (or first) element
Usually, each node only points to the next node
Doubly linked lists have a head and a tale element so the list can be accessed from either side
Each node can point to the previous and the next one, allowing you to traverse the list from the tail
Inserting takes O(1) time for doubly linked lists or O(n) time for singly linked lists, while inserting in place takes O(n) time.
Likewise, deleting the head (or tail in a doubly linked list) takes O(1) time while deleting in place is O(n)
Searching the structure for a node takes O(n) time
Memory-wise, the structure only takes up roughly O(n) space.
Alright, so let's discuss these runtimes. To have an example on hand, we'll use the following diagram as a representation of a singly linked list. Please not that the bolded integer is the head and the arrows are pointers to the next node.
5 -> 4 -> 11 -> 32 -> 2 -> 15 -> 4 -> NULL
First, I mentioned insertion. Insertion's runtime is all based on the linked list's implementation. If the implementation uses a tail node (doubly linked list), then insertion is just pointing the tail node to the new node and then swapping them. This should take constant time. To insert a node in a singly linked list, the structure has to go through all of the nodes until it gets to null and then appends the new node. This would obviously be in O(n) time.
Next, I mentioned deletion. Deletion's runtime is O(1) because it usually is implemented as removing the head or tail node, which would be O(1) time. To accomplish tail-end deletion, you would write a function that points the tail node's previous node's next node to NULL (say THAT 10x fast!). Though, deletion of a certain node would involve traversing to that node in the list, and then set the previous node's next node to its next node's next node. Yeah. Head hurting yet? Here's sample code on how to delete a specified value:
public Node deleteNode( Node head, int data) {
Node n = head;
if (n.data == data) {
return head.next; //Return LL without head node
}
while (n.next != null) {
if (n.next.data == data) {
n.next = n.next.next; //Delete n.next, which is the node we want
return head;
}
n = n.next;
}
return head;
}
Now, we went over a bit of searching in the code up there. If you remember, I noted that it's runtime is O(n). If you see how we traversed the linked list above, you would notice that we have to go to every node looking for a certain value. The worst case scenario in searching an n-long list for a value d is that d is at the end. That means we would have to go through the entire length of the list, which means search is dependent on the length of the list. Therefore, search is O(n).
Great, I understand how to implement one, but why?
Linked lists aren't inherently useful, themselves, but are useful in implementing other data structures. Both stacks and queues are often implemented using linked lists as their underlying structures. Also, a hash table can use a linked List to store the chain of items associated with the same hash value. Please note that these are just a few example usages of linked lists and are hardly the only use cases!
I realize I haven't implemented the entire class for a linked list, but I promise I'll upload the code soon! I'm trying to figure out how to upload code to Blogger without it looking insane, so hopefully there's a solution and it'll be up soon! Thanks for reading my first post, I hope to have many more soon!
